#include <stdio.h>
#include <stdlib.h>

typedef DataType int;
typedef enum bool Bool;
enum bool {
        false, true
};
struct LinkedList {
        DataType val;
        struct LinkedList *next;
};
typedef struct LinkedList *LinkedList;
typedef struct LinkedList *PNode;

struct LinkedSet {
        LinkedList *ptrlist;
        int len;
};
typedef struct LinkedSet *LinkSet;

LinkSet createEmptySet(void);
Bool isEmptySet(LinkSet head);
PNode Locate_Set(LinkSet head, DataType x);
int Set_Length(LinkSet head);
void InsertPost_Set(LinkSet head, PNode p, DataType x);
void DeleteAddress_Set(LinkSet head, PNode p);
LinkSet Set_Intersection(LinkSet head1, LinkSet head2);
LinkSet Set_Union(LinkSet head1, LinkSet head2);
LinkSet Set_Difference(LinkSet big, LinkSet small);

// 创建带头结点的链式集合.
LinkSet createEmptySet(void)
{
        LinkSet head = (LinkSet)malloc(sizeof(struct LinkedSet));
        head->ptrlist->next = NULL;
        head->len = 0;
        return head;
}

Bool isEmptySet(LinkSet head)
{
        return head->ptrlist->next == NULL;
}

// 判断x是否为集合的成员.
// 时间复杂度：O(n), 空间复杂度：O(1).
PNode Locate_Set(LinkSet head, DataType x)
{
        LinkSet p;
        for (p = head->ptrlist; p != NULL; p = p->next)
        {
                if (x == p->val)
                        return p;
        }
        return p;
}

// 求解集合的长度.
// 时间复杂度：O(n), 空间复杂度：O(1).
/* int Set_Length(LinkSet head)
{
        LinkSet p;
        int length = 0;
        for (p = head->next; p != NULL; p = p->next)
                length++;
        return length;
} */

void InsertPost_Set(PNode p, DataType x)
{
        PNode q = (PNode)malloc(sizeof(struct LinkSet));
        if (q == NULL) {
                printf("Out of memory!\n");
        }
        q->val = x;
        q->next = p->next;
        p->next = q;
}

void DeleteAddress_Set(LinkSet head, PNode p)
{
        PNode q = head->ptrlist;
        while (q->next != p && q->next != NULL)
                q = q->next;
        if (q->next == NULL) {
                printf("Not find it!\n");
        } else {
                PNode tmp = p;
                q->next = q->next->next;
                free(tmp);
        }
}

// 求交集.
LinkSet Set_Intersection(LinkSet head1, LinkSet head2)
{
        LinkSet head3;
        head3 = createEmptySet();
        // 使用双重for循环来查找相同元素.
        PNode p, q;
        for (p = head1->ptrlist; p != NULL; p = p->next) {
                for (q = head2->ptrlist; q != NULL; q = q->next) {
                        if (p->val == q->val) {
                                InsertPost_Set(head3->ptrlist, p->val);
                                head3->len++;
                        }
                }
        }
        return head3;
}

// 求并集. 时间复杂度：O(n^2), 空间复杂度: O(n), 和新开辟的集合长度有关.
LinkSet Set_Union(LinkSet head1, LinkSet head2)
{
        LinkSet head4;
        head4 = createEmptySet();
        PNode p, q;
        for (p = head1->ptrlist; p != NULL; p = p->next) {
                for (q = head2->ptrlist; q != NULL; q = q->next) {
                        if (p->val == q->val) {
                                break; // 只break一层循环.
                        }
                }
                InsertPost_Set(head4->ptrlist, p->val);
                head4->len++;
        }
        return head4;
}

// 求差集. 时间复杂度：O(n^2), 空间复杂度: O(n), 和新开辟的集合长度有关.
LinkSet Set_Difference(LinkSet big, LinkSet small)
{
        LinkSet head5;
        head5 = createEmptySet();
        PNode p, q;
        for (p = big->ptrlist; p != NULL; p = p->next) {
                for (q = small->ptrlist; q != NULL; q = q->next) {
                        if (p->val != q->val) {
                                InsertPost_Set(head5->ptrlist, p->val);
                                head5->len++;
                        }
                }
        }
        return head5;
}

// 先求出head1和head2两集合的并集，在分别判断并集和这两个集合是否相等.
// 若不相等，则false；反之，则true.
Bool Set_Is_Equal(LinkSet head1, LinkSet head2)
{
        // 对长度进行判断
        if (head1->len != head2->len) {
                return false;
        }
        LinkSet head6 = Set_Union(head1, head2);
        // 对长度进行判断
        if (head1->len != head6->len || head2->len != head6->len) {
                return false;
        }
        PNode p, q;
        for (p = head6->ptrlist; p != NULL; p = p->next) {
                for (q = head1->ptrlist; q != NULL; q = q->next) {
                        if (p->val != q->val) {
                                return false;
                        }
                }
        }
        for (p = head6->ptrlist; p != NULL; p = p->next) {
                for (q = head2->ptrlist; q != NULL; q = q->next) {
                        if (p->val != q->val) {
                                return false;
                        }
                }
        }
        return true;
}

Bool Set_Is_Subset(LinkSet big, LinkSet small)
{
        if (big->len < small->len) {
                return false;
        }
        LinkSet head7 = Set_Union(big, small);
        if Set_Is_Equal(big, head7) {
                return true;
        }
        return false;
}
